/*https://leetcode.cn/problems/number-of-digit-one/description/
233.数字1的个数
medium, 方钊堉 2024.10.07
数位DP*/

class Solution {
public:
    static const int MAX_DIGITS = 11;
    vector<int> digits; // 存储数字n的每一位
    int dpTable[MAX_DIGITS][10]; // 动态规划表

    // 计算数字n中1的个数
    int dp(int n) {
        if (n == 0) return 0;
        while (n) {
            digits.push_back(n % 10);
            n /= 10;
        }
        int result = 0;
        int lastDigit = 0;
        int oneCount = 0;
        for (int i = digits.size() - 1; i >= 0; --i) {
            int currentDigit = digits[i];
            if (oneCount > 0) result += pow(10, i) * currentDigit * oneCount;
            for (int j = 0; j < currentDigit; ++j) {
                result += dpTable[i + 1][j];
            }
            lastDigit = currentDigit;
            if (currentDigit == 1) oneCount++;
        }
        result += oneCount;
        return result;
    }

    // 计算数字n中1的个数
    int countDigitOne(int n) {
        for (int i = 0; i < 10; ++i) {
            dpTable[0][i] = 0;
        }
        for (int digitPosition = 1; digitPosition < MAX_DIGITS; ++digitPosition) {
            for (int currentDigit = 0; currentDigit < 10; ++currentDigit) {
                for (int previousDigit = 0; previousDigit < 10; ++previousDigit) {
                    dpTable[digitPosition][currentDigit] += dpTable[digitPosition - 1][previousDigit];
                }
                if (currentDigit == 1) {
                    dpTable[digitPosition][currentDigit] += pow(10, digitPosition - 1);
                }
            }
        }
        return dp(n);
    }
};